package com.zheng;

import java.util.*;

public class Tree {
    //树节点
    static class TreeNode {
        private TreeNode(char val) {
            this.val = val;
        }

        private char val;
        private TreeNode left;
        private TreeNode right;

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }


    public TreeNode test1;
    public TreeNode test2;

    //创建树
    public TreeNode createTree() {
        TreeNode treeNodeA = new TreeNode('A');
        TreeNode treeNodeB = new TreeNode('B');
        TreeNode treeNodeC = new TreeNode('C');
        TreeNode treeNodeD = new TreeNode('D');
        TreeNode treeNodeE = new TreeNode('E');
        TreeNode treeNodeF = new TreeNode('F');
        TreeNode treeNodeG = new TreeNode('G');
        TreeNode treeNodeH = new TreeNode('H');
        treeNodeA.left=treeNodeB;
        treeNodeA.right=treeNodeC;
        treeNodeB.left=treeNodeD;
        treeNodeB.right=treeNodeE;
        treeNodeD.right=treeNodeH;
        treeNodeC.left=treeNodeF;
        treeNodeC.right=treeNodeG;
        test1=treeNodeH;
        test2=treeNodeE;
        return treeNodeA;
    }

    //前序遍历
    public static void preOrder(TreeNode root) {
        if(root==null) return;
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    //将前序遍历的结果返回到集合当中

    //递归实现
    public List<Character> preorderTraversal1(TreeNode root) {
        ArrayList<Character> list = new ArrayList<>();
        if(root==null) return list;
        list.add(root.val);
        list.addAll(preorderTraversal1(root.left));
        list.addAll(preorderTraversal1(root.right));
        return list;
    }
    //非递归实现
    public List<Character> preorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Character> ret = new ArrayList<>();
        if(root==null) return ret;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            ret.add(pop.val);
            if(pop.right!=null) stack.push(pop.right);
            if(pop.left!=null) stack.push(pop.left);
        }
        return ret;
    }

    public List<Character> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Character> ret = new ArrayList<>();
        TreeNode tmp = root;
        while (tmp!=null|| !stack.isEmpty()) {
            while (tmp!=null) {
                stack.push(tmp);
                ret.add(tmp.val);
                tmp=tmp.left;
            }
            tmp=stack.pop();
            tmp=tmp.right;
        }
        return ret;
    }

//zzzyh
//    Stack<TreeNode> stack = new Stack<>();
//    List<Character> ret = new ArrayList<>();
//        if(root==null) return ret;
//    TreeNode tmp = root;
//        while (tmp!=null||!stack.isEmpty()) {
//        while(tmp!=null) {
//            stack.push(tmp);
//            tmp=tmp.left;
//        }
//        TreeNode peek = stack.peek();
//        if(peek.right==null||(ret.size()>0&&peek.right.val==ret.get(ret.size()-1))) {
//            stack.pop();
//            ret.add(peek.val);
//        }else{
//            tmp=peek.right;
//        }
//    }
//        return ret;

    //中序遍历
    public static void inOrder(TreeNode root) {
        if(root==null) return;
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }

    //非递归实现
    public List<Character> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Character> ret = new ArrayList<>();
        if(root==null) return ret;
        TreeNode tmp = root;
        while (tmp!=null||!stack.isEmpty()) {
            while(tmp!=null) {
                stack.push(tmp);
                tmp=tmp.left;
            }
            TreeNode pop = stack.pop();
            ret.add(pop.val);
            tmp=pop.right;
        }
        return ret;
    }

    //后序遍历
    public static void postOrder(TreeNode root) {
        if(root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }



    public List<Character> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Character> list = new LinkedList<>();
        if(root==null) return list;
        TreeNode tmp = root;

        while (tmp!=null||!stack.isEmpty()) {
            while(tmp!=null) {
                stack.push(tmp);
                tmp=tmp.left;
            }
            TreeNode peek = stack.peek();
            if(peek.right==null||(list.size()>0&&list.get(list.size()-1)==peek.right.val)) {
                TreeNode pop = stack.pop();
                list.add(pop.val);
            }else {
                tmp=peek.right;
            }
        }
        return list;
    }

    //获得树中节点的个数
    public static int size(TreeNode root) {
        int ret = 0;
        if(root==null) return 0;
        ret++;
        ret+=size(root.left);
        ret+=size(root.right);
        return ret;
    }

    // 获取叶子节点的个数
    public static int getLeafNodeCount(TreeNode root) {
        if(root==null) return 0;
        int ret = 0;
        if(root.left==root.right) return 1;
        else {
            ret+=getLeafNodeCount(root.left);
            ret+=getLeafNodeCount(root.right);
        }
        return ret;
    }

    // 获取第K层节点的个数
    public static int getKLevelNodeCount(TreeNode root,int k){
        if(root==null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        for (int i = 1; i < k; i++) {
            int sz = queue.size();
            while(sz--!=0) {
                TreeNode node = queue.poll();
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        int ret = 0;
        while(!queue.isEmpty()) {
            if(queue.poll()!=null) ret++;
        }
        return ret;
    }
    //获得k层接节点个数法二
    public static int getKLevelNodeCount1(TreeNode root,int k){
        if(root==null) return 0;
        if(k!=1) {
            return getKLevelNodeCount1(root.left,k-1)+getKLevelNodeCount1(root.right,k-1);
        } else return 1;
    }

    // 获取二叉树的高度
    public static int getHeight(TreeNode root){
        if(root==null) return 0;
        else {
            int left = getHeight(root.left);
            int right = getHeight(root.right);
            return 1+Math.max(left, right);
        }
    }
    // 检测值为value的元素是否存在
    public static TreeNode find(TreeNode root, int val){
        if(root==null) return null;
        else if(root.val==val) return root;
        TreeNode ret =  find(root.left,val);
        if(ret != null) return ret;
        ret =  find(root.right,val);
        if(ret != null) return ret;
        return null;
    }
    //层序遍历
    public static void levelOrder(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
            System.out.println(poll.val);
        }
    }
    //将层序遍历的结果放入二维数组，按层区分
    public static List<List<Character>> levelOrder1(TreeNode root) {
        List<List<Character>> arrayLists = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null) return arrayLists;
        queue.offer(root);
        while(!queue.isEmpty()){
            ArrayList<Character> arrayList = new ArrayList<>();
            int sz= queue.size();
            while(sz--!=0) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
                arrayList.add(poll.val);
            }
            arrayLists.add(arrayList);
        }
        return arrayLists;
    }

    //输出二叉树的左视图
    public static void zuoshi(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null) return;
        queue.offer(root);
        while(!queue.isEmpty()){
            int sz= queue.size();
            int cpy = sz;
            while(sz--!=0) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
                if(sz==cpy-1) System.out.println(poll.val);
            }
        }
    }

    //输出二叉树的宽
    public static int kuan(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null) return 0;
        queue.offer(root);
        int ret = 0;
        while(!queue.isEmpty()){
            int sz= queue.size();
            if(sz>ret) ret=sz;
            while(sz--!=0) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
        }
        return ret;
    }

    // 判断一棵树是不是完全二叉树
    public static boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null) return true;
        queue.offer(root);
        while(true){
            int sz= queue.size();
            while(sz--!=0) {
                TreeNode poll = queue.poll();
                if(poll==null) {
                    while(!queue.isEmpty()) {
                        if(queue.poll()!=null) return false;
                    }
                    return true;
                }
                queue.add(poll.left);
                queue.add(poll.right);
            }
        }
    }

    //判断一棵树是否为另一棵树的子树
    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(isSameTree(root,subRoot)) return true;
        if(root==null) return false;
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
    //判断两棵树是否相等
    private static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null) return true;
        else if (p==null|| q==null) return false;
        if(p.val!=q.val) return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

    //翻转二叉树
    public static TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        if(root.left==null&&root.right==null) return root;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }

    //找到两颗数的最近公共祖先
    public static TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        TreeNode ret = root;
        TreeNode rem=null;
        if(findnode(root,p)&&findnode(root,q)) {
            rem =lowestCommonAncestor1(root.left, p, q);
            if(rem!=null) return rem;
            rem=lowestCommonAncestor1(root.right,p,q);
            if(rem!=null) return rem;
        }else {
            return null;
        }
        return ret;
    }

    //判断root节点下是否有p节点
    public static boolean findnode(TreeNode root, TreeNode p){
        if(p==null) return true;
        if(root==null) return false;
        else if(root==p) return true;
        return findnode(root.left,p)||findnode(root.right,p);
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root==p||root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null) return root;
        else if(left==null) return right;
        else return left;
    }


}